package com.fengdi.book.hard;

import java.util.*;

public class ArraysAndString {
    public static class ProductExceptSelf {
        public int[] productExceptSelf(int[] nums) {
            if (nums.length == 0) return nums;
            if (nums.length == 1) return new int[]{0};
            // 时间复杂度为O(n^2)会超时
            int[] result = new int[nums.length];
            int len = nums.length;
            //for(int i = 0; i < nums.length; i++) {
            //    int temp = 1;
            //    for (int j = 0; j < nums.length; j++) {
            //        if (i == j) continue;
            //        temp *= nums[j];
            //    }
            //    res[i] = temp;
            //}
            int tmp = 1;
            for (int left = 0; left < len; ++left) {
                result[left] = tmp;
                tmp = tmp * nums[left];
            }

            tmp = 1;
            for (int right = len - 1; right >= 0; --right) {
                result[right] *= tmp;
                tmp *= nums[right];
            }


            return result;
        }
    }

    public static class SpiralOrder {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> result = new ArrayList<>();
            if(matrix == null || matrix.length == 0) {
                return result;
            }
            int m = matrix.length;
            int n = matrix[0].length;

            int up = 0;// 上边界
            int down = m - 1; // 下边界
            int left = 0;// 左边界
            int right = n - 1;// 右边界
            int total = m * n;
            while(result.size() < total) {
                for(int i = left; i <= right && result.size() < total; i++) {
                    result.add(matrix[up][i]);
                }

                for(int i = up + 1; i < down && result.size() < total; i++) {
                    result.add(matrix[i][right]);
                }

                for(int i = right; i >= left && result.size() < total; i--) {
                    result.add(matrix[down][i]);
                }

                for(int i = down - 1; i > up && result.size() < total; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
                right--;
                up++;
                down--;
            }

            return result;
        }
    }

    public static class FourSumCount {
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
            /**
             * map1 是 nums1 和 nums2每对元素的和
             * map2 是 nums3 和 nums4每对元素的和
             * 当 map 中有相反的元素时，则表示四个数组中的元素之和为 0
             * */
            Map<Integer, Integer> map1 = new HashMap<>();
            Map<Integer, Integer> map2 = new HashMap<>();
            int result = 0;
            this.getSum(nums1, nums2, map1);
            this.getSum(nums3, nums4, map2);
            for(Integer key : map1.keySet()) {
                if(map2.containsKey(-key)) {
                    result += map1.get(key) * map2.get(-key);
                }
            }

            return result;
        }

        private void getSum(int[] nums1, int[] nums2, Map<Integer, Integer> map) {
            for (int j : nums1) {
                for (int k : nums2) {
                    int sum = j + k;
                    if (map.containsKey(sum)) {
                        map.put(sum, map.get(sum) + 1);
                    } else {
                        map.put(sum, 1);
                    }
                }
            }
        }
    }

    public static class MaxArea {
        public int maxArea(int[] height) {
            int res = 0;
            int left = 0;
            int right = height.length - 1;
            while(left < right) {
                int min = Math.min(height[left], height[right]);
                res = Math.max(res, min * (right - left));
                if(height[left] > height[right]) {
                    right--; // 左边的板子比右边高，如果想要容积继续上升，在宽度减小的情况下只有板子变高才有可能继续上升
                }else {
                    left++;
                }
            }
            return res;
        }
    }

    public static class GameOfLife {
        public void gameOfLife(int[][] board) {
            int[][] help = new int[board.length][board[0].length];
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    help[i][j] = board[i][j];
                }
            }
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    int live = convolutionKernel_3X3(help, i, j);
                    if(board[i][j] == 1) {
                        board[i][j] = live == 3 || live == 2 ? 1 : 0; // 活细胞，只有当邻居存活数小于2或者大于3时，该位置死亡
                    }else {
                        board[i][j] = live == 3 ? 1 : 0; // 死细胞，只有当邻居存活数等于3时，该位置复活
                    }
                }
            }
        }

        /**
         * @author FengDi
         * @description 利用3X3卷积核来计算当前位置的邻居存活状态
         * @param
         * @return
         * @Date 2025/4/21
         * */
        private int convolutionKernel_3X3(int[][] board, int row, int col) {
            int count =0;
            int[][] kernel = {
                    {1, 1, 1},
                    {1, 0, 1},
                    {1, 1, 1}
            };

            int[][] output = {
                    {0, 0, 0},
                    {0, 0, 0},
                    {0, 0, 0}
            };

            for(int i = 0; i < 3; i++) {
                int currentRow = row - 1 + i;
                if (currentRow < 0 || currentRow >= board.length) {// 判断当前行是否超界
                    continue;
                }else {
                    output[i][0] = col - 1 >= 0 ? board[currentRow][col - 1] * kernel[i][0]: 0;
                    output[i][1] = board[currentRow][col] * kernel[i][1];
                    output[i][2] = col + 1 < board[0].length ? board[currentRow][col + 1] * kernel[i][2]: 0;
                }
            }

            for(int i = 0; i < 3; i++) {
                for(int j = 0; j < 3; j++) {
                    count += output[i][j];
                }
            }

            return count;
        }
    }

    public static class LongestConsecutive {
        public int longestConsecutive(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            if(nums.length == 1) return 1;

            Arrays.sort(nums);
            int res = 1;
            int temp = nums[0];
            int length = 0;
            for (int num : nums) {
                if (temp == num) {
                    length++;
                    temp++;
                }else if(num == temp - 1) {
                    continue;
                } else {
                    temp = num + 1;
                    length = 1;
                }
                if (length > res) {
                    res = length;
                }

            }
            return res;
        }
    }

    public static class FindDuplicate {
        public int findDuplicate(int[] nums) {
            if (nums == null || nums.length <= 1) return -1;
            Arrays.sort(nums);
            for(int i = 1; i < nums.length; i++) {
                if(nums[i] == nums[i - 1]) { // 说明是重复元素
                    return nums[i];
                }
            }

            return -1;
        }
    }

    public static class Calculate {
        private final HashMap<Character, Integer> SYMBOL_TABLE = new HashMap<>();

        /**
         * @Description 计算后缀表达式
         * @Date 2025/4/28
         * @param s 计算式字符串
         * @return  计算结果
         */

        public int calculate(String s) {
            this.SYMBOL_TABLE.put('+', 1);
            this.SYMBOL_TABLE.put('-', 1);
            this.SYMBOL_TABLE.put('*', 2);
            this.SYMBOL_TABLE.put('/', 2);
            this.SYMBOL_TABLE.put('(', 0);
            ArrayList<String> postfix = this.getPostfix(s);
            System.out.println(postfix);
            // 计算后缀表达式
            Stack<Integer> numStack = new Stack<>();

            for(String c : postfix) {
                if(this.isNumeric(c)) {
                    try {
                        int digit = Integer.parseInt(c);
                        numStack.push(digit);
                    }catch (NumberFormatException e) {
                        System.out.println("数字格式化异常");
                    }
                }else {
                    int x = numStack.pop();
                    int y = numStack.pop();
                    switch(c) {
                        case "+": numStack.push(y + x); break;
                        case "-": numStack.push(y - x); break;
                        case "*": numStack.push(y * x); break;
                        case "/": numStack.push(y / x); break;
                        default: break;
                    }
                }
            }
            return numStack.pop();
        }

        /**
         * @Description 根据字符串计算式生成后缀表达式
         * @Date 2025/4/28
         * @param s 字符串计算式
         * @return  后缀表达式
         */
        private ArrayList<String> getPostfix(String s) {
            StringBuilder digital_sb = new StringBuilder();
            Stack<Character> stack = new Stack<>();
            ArrayList<String> list = new ArrayList<>();


            for(Character c : s.toCharArray()) {
                if (c == ' ') continue;

                if(Character.isDigit(c)) {
                    digital_sb.append(c);
                }else {
                    if(!digital_sb.isEmpty()) {
                        list.add(digital_sb.toString());
                        digital_sb.setLength(0);
                    }

                    if(c == '(') {
                        stack.push(c);
                    }else if(c == ')') {
                        while(!stack.isEmpty() && stack.peek() != '(') {
                            list.add(stack.pop().toString());
                        }
                        stack.pop();
                    }else{ // 是运算符
                        if(stack.isEmpty()) {
                            stack.push(c);
                        }else {
                            if (this.isPriority(c, stack.peek())) { // 判断当前元素的优先级是否大于栈顶元素
                                stack.push(c); // 如果大于栈顶元素，直接入栈
                            }else {
                                do{
                                    list.add(stack.pop().toString());
                                }while(!stack.isEmpty() && !this.isPriority(c, stack.peek()));
                                stack.push(c);
                            }
                        }
                    }
                }
            }
            if (!digital_sb.isEmpty()) list.add(digital_sb.toString());

            while (!stack.isEmpty()) {
                list.add(stack.pop().toString());
            }
            return list;
        }

        private boolean isPriority(char c1, char c2) {
            return this.SYMBOL_TABLE.get(c1) > this.SYMBOL_TABLE.get(c2);
        }

        public boolean isNumeric(String str) {
            return str.matches("-?\\d+(\\.\\d+)?");  // 匹配整数和小数
        }
    }

    public static class MaxSlidingWindow {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(k > nums.length) return new int[0];
            int[] result = new int[nums.length - k + 1];
            for(int i = 0; i < nums.length - k + 1; i++) {
                result[i] = getMax(nums, i, i + k);
            }

            return result;
        }

        private int getMax(int[] nums, int start, int end) {
            int max = nums[start];
            for(int i = start + 1; i < end; i++) {
                if(nums[i] > max) {
                    max = nums[i];
                }
            }

            return max;
        }
    }

    public static class FirstMissingPositive {
        public int firstMissingPositive(int[] nums) {
            if (nums == null || nums.length == 0) return 1;
            nums = this.removeDuplicates(nums); // 去重
            Arrays.sort(nums);// 排序
            // 找到第一个大于0的数，如果找不到，则返回1
            int index = 0;
            int i = 0;
            for (; i < nums.length; i++) {
                if (nums[i] > 0) {
                    index = i;
                    break;
                }
            }
            if (i == nums.length || nums[index] != 1) return 1;

            int result = nums[index];
            for (int j = index; j < nums.length; j++) {
                if (result != nums[j]) {
                    return result;
                } else {
                    result++;
                }
            }
            return result;
        }

        public int[] removeDuplicates(int[] array) {
            return Arrays.stream(array).distinct().toArray();
        }
    }

    public static class MinWindow {
        public String minWindow(String s, String t) {
            if (s == null || t == null || s.length() < t.length()) return "";
            Map<Character, Integer> map = new HashMap<>();
            String result = "";
            for (char c : t.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }

            int begin = 0;
            for (; begin <= s.length() - t.length(); begin++) {
                int left = begin;
                int right = left + t.length() - 1;
                while (right <= s.length() && !this.isValid(s.substring(left, right), map)) {
                    right++;
                }

                if (right > s.length()) { // 窗口右边界超出字符串长度，则返回空串
                    System.out.println(begin);
                    System.out.println(right);
                    System.out.println(s.substring(left, right - 1));
                    break;
                }

                while (left < right && this.isValid(s.substring(left, right), map)) {
                    left++;
                }
                left--;
                if (result.isEmpty() || right - left < result.length()) {
                    result = s.substring(left, right);
                }

            }
            return result;
        }

        private boolean isValid(String s, Map<Character, Integer> map) {
            Map<Character, Integer> temp = new HashMap<>();
            for (char c : s.toCharArray()) {
                temp.put(c, temp.getOrDefault(c, 0) + 1);
            }

            for (Character c : map.keySet()) {
                if (temp.get(c) == null ||temp.get(c) < map.get(c)) return false;
            }

            return true;
        }
    }


}
